#pragma once
#include <functional>

/**
 * 快速排序的分割子程序，其也是快排的核心要点所在.
 * 每次的调用都会使得序列中某一元素在正确的相对位置上，其左侧与右侧符合比较式.
 * @param nFirst需要分割的首元素下标索引
 * @param nLast需要分割的尾元素下标索引
 * @return 返回的是已经被处理（放置到正确的位置上）好的元素的下标索引
 */
template<typename T,typename compare = std::less_equal<T>>
int Partition(T* pElems, int nFirst, int nLast){
    int nPreLast = nLast - 1;
    compare comp;
    int nOffset = nFirst - 1;
    for(int i = nFirst; i <= nPreLast; ++i){
        if(comp(pElems[i], pElems[nLast])){
            nOffset += 1;
            std::swap<T>(pElems[i], pElems[nOffset]);
        }
    }
    std::swap(pElems[++nOffset], pElems[nLast]);
    return nOffset;
}

/**
 * 快速排序
 * 每次只确认一个元素应该放置的位置.
 */
template<typename T, typename compare = std::less_equal<T>>
void QuickSort(T* pElems, int nFirst, int nLast){
    if(nFirst < nLast){
        int nOffset = Partition<T, compare>(pElems, nFirst, nLast);
        //nOffset索引处的值已经确认，所以无需再排序了, 可见 -1, +1　就跳过这个元素了.
        QuickSort<T, compare>(pElems, nFirst, nOffset - 1);
        QuickSort<T, compare>(pElems, nOffset + 1, nLast);
    }
}